package leetcode;

/**
 * Created by Ghost on 2014/11/19 0019.
 */
public class Reverse_Nodes_in_k_Group {
    private void reverse(ListNode pre, ListNode head, ListNode end) {
        ListNode p = pre;
        ListNode cur = head;
        while (cur != end) {
            ListNode tmp = cur.next;
            if (cur == head)
                cur.next = end.next;
            else
                cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        cur.next = pre;
        if (p != null)
            p.next = cur;
    }

    private ListNode searchHead(ListNode head, int k) {
        int count = 0;
        ListNode cur = head;
        while (cur != null && count < k) {
            count++;
            if (count == k)
                return cur;
            cur = cur.next;
        }
        return head;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if(k<=1)
            return head;
        ListNode newHead = searchHead(head, k);
        if (newHead == head)
            return newHead;

        int count = 0;
        ListNode cur = head;
        ListNode curHead = head;
        ListNode preHead = null;
        while (cur!=null) {
            count++;
            if (count == k) {
                ListNode nextBegin = cur.next;
                reverse(preHead, curHead, cur);
                cur = nextBegin;
                preHead = curHead;
                count = 0;
            } else {
                if (count == 1)
                    curHead = cur;
                cur = cur.next;
            }
        }
        return newHead;
    }

    public static void main(String[] args){
        Reverse_Nodes_in_k_Group reverse_nodes_in_k_group = new Reverse_Nodes_in_k_Group();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        head.next.next.next.next.next.next = new ListNode(7);
        head.next.next.next.next.next.next.next = new ListNode(8);

        ListNode cur = reverse_nodes_in_k_group.reverseKGroup(head,0);
        while(cur!=null){
            System.out.print(" "+cur.val);
            cur = cur.next;
        }
    }
}
